﻿#include <iostream>
using namespace std;

const int n = 5;

int dataTower(int d[n][n]) {			//求数塔问题，数塔存储在数组d[n][n]中
	int maxAdd[n][n] = {0};				//初始化
	int path[n][n] = {0};
	int i, j;
	for(j = 0; j < n; j++) {			//初始化底层决策结果
		maxAdd[n - 1][j] = d[n - 1][j];
	}
	for(i = n - 2; i >= 0; i--) {		//进行第i层的决策
		for(j = 0; j <= i; j++) {		//填写addMax[i][j]，只填写下三角
			if(maxAdd[i + 1][j] > maxAdd[i + 1][j + 1]) {
				maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j];
				path[i][j] = j;			//本次决策选择下标j的元素
			} else {
				maxAdd[i][j] = d[i][j] + maxAdd[i + 1][j + 1];
				path[i][j] = j + 1;		//本次决策选择下标j+1的元素
			}
		}
	}
	cout << "路径为：" << d[0][0];		//输出顶层数字
	j = path[0][0];						//顶层决策是选择下一层列下标为path[0][0]的元素
	for(i = 1; i < n; i++) {
		cout << "-->" << d[i][j];
		j = path[i][j];					//本层决策是选择下一层列下标为path[i][j]的元素
	}

	return maxAdd[0][0];				//返回最大数值和，即最终的决策结果
}

int main() {
	int d[n][n] = {
		8, 0, 0, 0, 0,
		12, 15, 0, 0, 0,
		3, 9, 6, 0, 0,
		8, 10, 5, 12, 0,
		16, 4, 18, 10, 9
	};
	cout << endl << "数塔的最大数值和是：" << dataTower(d) << endl;

	system("pause");
	return 0;
}